Problématique de l'apprentissage par renforcement¶

1. Concept et terminologie¶

L'apprentissage par renforcement (Reinforcement Learning - RL) est une discipline distincte du Machine Learning. Dans le cadre du RL, on définit un agent (par exemple un robot) et un environnement (l'environnement du robot). L'environnement est représenté par des états - ensemble de variables qui définissent complètement l'environnement. L'agent peut éventuellement connaître totalement l'environnement ou juste à une partie de celui-ci. Dans tous les cas, par des observations, l'agent peut avoir accès à des données de l'environnement.

A chaque instant, l'agent est en interaction avec l'environnement, en effectuant certaines actions (par exemple un déplacement dans une direction particulière). Ces actions sont effectuées en suivant une politique (policy) qui détermine quelles actions prendre dans l'environnement. Cette politique est en quelque sorte le "cerveau" de l'agent et dicte les règles qu'il doit suivre pour se déplacer dans l'environnement. Normalement, le nombre d'actions qu'un agent peut suivre sur chaque état est constant mais peut éventuellement varier. L'ensemble des actions possibles pour l'ensemble des états est nommé l'espace des actions.

L'agent, qui interagit avec l'environnement (par observation de l'environnement et en prenant certaines actions) reçoit une somme de récompenses. Ces récompenses sont accumulées à chaque fois qu'une action est effectuée par l'agent. Le revenu global est donc la somme des récompenses accumulées :

$${G_t} = {r_1} + {r_2} + {r_3} + ... + {r_T} = \sum\limits_{t = 1}^T {{r_t}}$$

Toutefois, ce calcul traite les récompenses obtenues à chaque transition de manière égale. On préfère donc donner un poids à chaque récompense afin de contrôler l'importance de chacune d'entre elles grace au facteur de remise $\gamma$ :

$${G_t} = {r_1} + \gamma {r_2} + {\gamma ^2}{r_3} + ... + {\gamma ^T}{r_T} = \sum\limits_{t = 1}^T {{\gamma ^{t - 1}}{r_t}} \quad avec \quad 0 \le \gamma \le 1$$

Si $\gamma = 1$ alors toutes les récompenses obtenues ont la même importance et si $\gamma = 0$ alors la récompense immédiate est la plus importante. Ceci peut être vu comme le fait que quelques fois les expériences immédiates ont plus d'importance que les expériences futures.

L'objectif de l'agent est de maximiser le revenu global, c'est-à-dire la somme des récompenses obtenues. L'agent va apprendre les meilleurs comportements (actions) à adopter pour atteindre ce but. L'apprentissage par renforcement est basé sur ce concept. Généralement, tous les algorithmes de d'apprentissage par renforcement essayent de résoudre un problème en maximisant le revenu que l'agent peut collecter.

Chaque action prise par l'agent influence l'environnement. L'environnement répond aux actions de l'agent en le faisant passer d'un état à un autre état. La fonction qui permet de réaliser ces transitions est la fonction de transition.

Les actions, états, transitions et les récompenses déterminent un processus de décision Markovien (Markov Decision Process - MDP). Dans le cadre de l'apprentissage par renforcement, on assume que les environnements sont modélisables par des MDP.

2. Fonctionnement de l'apprentissage par renforcement¶

Tout d'abord, l'agent interagit avec son environnement afin de récupérer des informations pour l'aider à apprendre. Il est donc dans un état d'interaction. Ensuite, en fonction des actions prises et des récompenses obtenues, l'agent évalue son comportement (sa politique, ses règles ou encore sa stratégie). L'agent est donc ici dans un état d'évaluation. Enfin, l'agent passe ensuite dans un état d'apprentissage afin d'améliorer ses décisions pour obtenir de meilleures performances.

Exemple

Considérons la situation théorique dans laquelle un robot se déplace dans un labyrinthe et tente de trouver une porte de sortie (objectif). Le robot doit apprendre le plus court chemin permettant d'atteindre cet objectif. Dans le labyrinthe, il y a également plusieurs pièges. Si le robot tombe dans l'un d'entre eux, des réparations devront être effectuées. De plus, à chaque fois que le robot tombe dans un piège, celui-ci disparaît et réapparaît à un autre endroit. Le robot peut avancer, reculer, aller à gauche ou à droite.

Dans ce cas, les analogies avec l'apprentissage par renforcement sont les suivantes :

Agent: Programme exécuté dans le CPU du robot (cerveau du robot)
Environnement : Labyrinthe dans lequel le robot évolue
Espace d'actions : Avancer, reculer, aller à gauche, aller à droite
Récompense : Si le robot atteint la sortie, il gagne +1. Chaque fois que le robot tombe dans un piège, il reçoit -1.
Observation : Si le robot tombe dans un piège, les pièges sont reformées à un autre endroit.
État : Position du robot dans le labyrinthe, carte courante du labyrinthe
Changement (transition) d'état : Changement de la carte lorsque le robot tombe dans un piège.

3. Autres concepts liés à l'apprentissage par renforcement¶

Comme nous l'avons vu précédemment, l'agent interagit avec son environnement en effectuant des actions. Suite à ces actions, l'environnement change éventuellement d'état. L'agent reçoit une récompense (positive ou négative). Le temps écoulé entre deux actions prises par l'agent s'appelle le pas de temps (time step) et l'ensemble {état, action, récompense} se nomme une expérience.

L'agent, en essayant de "gagner la partie" (remporter le plus de gain possible) apprend une stratégie (ou politique) (c'est-à-dire comment effectuer les actions dans le meilleur ordre possible pour accumuler le plus de récompenses). L'apprentissage peut se dérouler sur plusieurs taches (parties de jeu). Les parties qui s'arrêtent naturellement (comme par exemple si le robot tombe dans le piège et qu'il est détruit) sont des taches épisodiques. Dans le cas contraire, on parle de taches continues. Il y a des tâches qui continuent éternellement (sans état terminal). Il peut s'agir par exemple d'un robot formé pour faire du trading. La beauté de l'apprentissage par renforcement est que l'agent apprend par lui-même comment interragir avec l'environnement dans le but d'atteindre son objectif. L'agent découvre la stratégie optimale (optimal policy). Ce n'est pas nous (humain) qui programmons la trajectoire du robot. Nous délivrons juste un algorithme qui détermine comment l'agent communique avec son environnement. Cette différence est fondamentale.

Maintenant que nous avons parlé du concept de récompense, voyons comment est définit la fonction du revenu global. A chaque instant, ce revenu est fonction de l'état courant de l'environnement, de l'action qui vient d'être prise par l'agent et de l'état suivant qui est influencé par l'action prise par l'agent :

$${r_t} = R\left( {{s_t},{a_t},{s_{t + 1}}} \right)$$

Cette fonction est quelquefois simplifiée et ne fait intervenir que l'état courant:

$${r_t} = R\left( {{s_t}} \right)$$

Ou la paire état-action :

$${r_t} = R\left( {{s_t},{a_t}} \right)$$

Les séquences des états et des actions sont appelées des trajectoires :

$$\tau = \left( {{s_0},{a_0},{s_1},{a_1},...} \right)$$

Comme nous l'avons vu, l'objectif est de maximiser le cumul des récompenses obtenues lors d'une trajectoire :

$${G_t} = \sum\limits_{t = 1}^T {{\gamma ^{t - 1}}{r_t}} \quad avec \quad 0 \le \gamma \le 1$$

$\gamma$ est le facteur de remise et $T$ est l'horizon qui peut être infini.

Pour l'agent, il est préférable de recevoir la récompense plus tôt que tard. Cela s'explique par le fait qu'une récompense future que peut recevoir l'agent est incertaine. Mathématiquement, cela est pris en compte par le facteur de remise $\gamma$, qui décroit de manière exponentielle avec le temps :